"""
算法思想：每次从无序部分选择最小（或最大）的元素，与无序部分的第一个元素交换位置，使有序部分逐渐扩大。

代码解释：
外层循环控制有序部分的长度，共需n-1趟（最后一个元素自然有序）。
min_index记录无序部分（[i, n-1]）中最小元素的索引，初始为i。
内层循环遍历无序部分，更新min_index找到真正的最小元素索引。
交换arr[i]和arr[min_index]，将最小元素加入有序部分。
时间复杂度：无论最好、最坏还是平均情况，均为O(n²)，但交换次数较少（最多n-1次）。
"""


def selection_sort(arr):
    n = len(arr)
    # 外层循环控制有序部分的长度（0到n-2）
    for i in range(n - 1):
        # 记录无序部分中最小元素的索引
        min_index = i

        # 内层循环查找无序部分的最小元素
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j

        # 将最小元素与无序部分的第一个元素交换
        arr[i], arr[min_index] = arr[min_index], arr[i]

    return arr


# 测试
arr = [64, 25, 12, 22, 11]
sorted_arr = selection_sort(arr)
print("简单选择排序结果:", sorted_arr)  # 输出: [11, 12, 22, 25, 64]
